--
-- Created by IntelliJ IDEA.
-- User: WenYF
-- Date: 2019/1/5 0005
-- Time: 下午 8:28
-- To change this template use File | Settings | File Templates.
-- A星 寻路


local FindPath = {}
-- 是否使用八个方向
local USE_EIGHT_DIRECTION = false


local tx
if USE_EIGHT_DIRECTION then
-- 八方向移动
tx = {
    [0] = {x=1, y=0},
    [1] = {x=1, y=1},
    [2] = {x=0, y=1},
    [3] = {x=-1,y=1},
    [4] = {x=-1,y=0},
    [5] = {x=-1,y=-1},
    [6] = {x=0, y=-1},
    [7] = {x=1, y=-1},
}

else
-- 四方向移动
tx = {
    [0] = {x=1, y=0},
    [1] = {x=0, y=1},
    [2] = {x=-1, y=0},
    [3] = {x=0, y=-1},
}
    
end

-- 优化close所有，直接通过key来判断新的点是否在close列表中
local function Close()
    --以数据为key，数据在set中的位置为value
    local hashMap = {}
    --一个数组，其中的value就是要管理的数据
    local set = {} 
    return setmetatable(set,{__index = {
        insert = function(set,pos)
            local key = tostring(pos.x) .. "_" .. tostring(pos.y)
            if not hashMap[key] then
                table.insert(set,pos)
                hashMap[key] = pos
            end
        end,

        find = function(set,x,y)
            local key = tostring(x) .. "_" .. tostring(y)
            local pos = hashMap[key]
            return (pos and true or false)
        end,
    }})
end

-- 相邻两个点移动值，A点到B点的移动值
-- 例如沼泽、草地等不同
local function GValue(a, b, grid)
    -- TODO G值
    if USE_EIGHT_DIRECTION then
        return a.g + math.sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y))
    end
    return a.g + math.abs(a.x - b.x) + math.abs(a.y - b.y)
end
-- 估算值，A点到目标点的距离
local function HValue(a, t, grid)
    return math.abs(a.x - t.x) + math.abs(a.y - t.y)
end
-- 是否相邻
local function neighbor(a, b)
    if USE_EIGHT_DIRECTION then
        local distance = math.sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y))
        return distance >= 1 and distance < 2
    end
    return math.abs(a.x - b.x) + math.abs(a.y - b.y) == 1
end

-- 添加open点
local function addOpen(open, newChoose)
    table.insert(open, newChoose)
end
-- 选择一个最优点
local function chooseOpen(open) 
    -- TODO 可以优化，这里是作用的穷举遍历
    local retPos = nil
    local chooseIdx = #open
    for idx=#open, 1, -1 do
        local pos = open[idx]
        if retPos == nil then
            retPos = pos
            chooseIdx = idx
        else
            if retPos.f > pos.f then
                retPos = pos
                chooseIdx = idx
            end
        end
    end

    if retPos ~= nil then
        table.remove(open, chooseIdx)
    end

    return retPos
end

-- 通过XY 得到open中的可选点
local function getOpen(open, x, y)
    for idx=#open, 1, -1 do
        local pos = open[idx]
        if pos ~= nil and pos.x == x and pos.y == y then
            return pos
        end
    end

    return nil
end

-- 添加close点
local function addClose(close, choose)
    close:insert(choose)
    --table.insert(close, choose)
end

-- 是否在close中
local function isInClose(close, x, y)
    local find = close:find(x, y)
    if find or false then
        return true    
    end
    
--    for idx=#close, 1, -1 do
--        local pos = close[idx]
--        if pos.x == x and pos.y == y then
--            return true
--        end
--    end

    return false
end

-- 在close反向寻找路径
local function findPathInClose(close)
    local path = {}
    local last = nil
    for idx=#close,1,-1 do
        if last == nil then
            last = close[idx]
            table.insert(path, last)
        else
            if neighbor(last, close[idx]) then
                last = close[idx]
                table.insert(path, last)
            end
        end
    end
    
    return path
end

-- 遍历路径
-- open 没有遍历过的点
-- close 已经遍历过的点
local function findPath(target, open, close, grid, callback, show)
    -- 得到一个最优决策点
    local choose = chooseOpen(open)
    if choose == nil then
        -- 已经遍历完所有open点
        return close
    end
    
    -- 加入到close列表
    addClose(close, choose)
    if callback ~= nil then
        callback(close, open)
    end
    
    -- 是否是终点
    if choose.x == target.x and choose.y == target.y then
        if callback ~= nil then
            callback(findPathInClose(close))
        end
        return close
    end
    
    -- 和choose相关联的可选点
    for k,v in pairs(tx) do
        while true do
            local x = choose.x + v.x
            local y = choose.y + v.y
            
            -- 以下的范围检测，可以通过地图设计规避，地图周围全部置位0
        --        if y > #grid or y < 0 then
        --            -- 超出范围
        --            if x > #grid[y] or x < 0 then
        --                -- 超出范围
        --            else
        --                -- 在grid范围内
        --            end
        --        end
            if grid[y][x] == 0 then
                -- 不能通过，不管 
                break
            end
                
            if isInClose(close, x, y) then
                -- 不管
                break
            end

            local newChoose = getOpen(open, x, y)
            if newChoose == nil then
                newChoose = {x=x,y=y}
                addOpen(open, newChoose)
            end
            -- 计算和值
            newChoose.g = GValue(choose, newChoose, grid)
            newChoose.h = HValue(newChoose, target, grid)
            newChoose.f = newChoose.g + newChoose.h
            break
        end
    end

    if show or false then
        local one = function()
            return findPath(target, open, close, grid, callback, show)
        end
        table.insert(FindPath.func, one)
    else
        return findPath(target, open, close, grid, callback, show)
    end
end


-- 找到最优路径
-- originA = {x,y}  起始点
-- targetB = {x,y}  目标点
-- grid是二维数组，0不能穿过，其他能穿过
-- callback: close列表和open回调
-- sleepTime: show为true的时候，每次遍历间隔时间
-- show 用来可视化
-- 返回最优路径
function FindPath:find(originA, targetB, grid, callback, sleepTime, show)
    -- 初始化第一个open点
    local open = {}
    -- 初始化第一个点的和值F
    originA.g = 0
    originA.h = HValue(originA, targetB, grid)
    originA.f = originA.g + originA.h
    addOpen(open, originA)
    -- 初始化close
    local close = Close()
    -- 开始遍历
    if show or false then
        self.func = {}
        local one = function()
            findPath(targetB, open, close, grid, callback, show)
        end
        table.insert(self.func, one)
        self.lastTime = os.clock()
        scene:getScheduler():scheduleScriptFunc(function(dt)
            if os.clock() - self.lastTime > sleepTime then
                local func = table.remove(self.func, 1)
                if func ~= null then
                    func()
                end
            end
        end, 0, false)
    else
        findPath(targetB, open, close, grid, callback, show)
        local optimalPath = findPathInClose(close)
        return optimalPath
    end
end

return FindPath

